package org.usmile.algorithms.knapsack;

public class _0_1_Knapsack3 {
    public int solve(int[] weights, int[] values, int capacity) {
        int[][] dp = new int[weights.length][capacity + 1];
        for (int c = 0; c <= capacity; c++) {
            dp[0][c] = (weights[0] <= c) ? values[0] : 0;
        }

        for (int i = 1; i < weights.length; i++) {
            for (int c = 0; c <= capacity; c++) {
                if (weights[i] > c) {
                    dp[i][c] = dp[i - 1][c];
                } else {
                    dp[i][c] = Math.max(dp[i - 1][c], dp[i - 1][c - weights[i]] + values[i]);
                }
            }
        }

        return dp[weights.length - 1][capacity];
    }


    public static void main(String[] args) {
        _0_1_Knapsack3 k = new _0_1_Knapsack3();
        int[] w = {3, 4, 5, 2};
        int[] v = {15, 10, 12, 8};
        System.out.println(k.solve(w, v, 10));
    }
}
